// 2025/10/28
// 二进制求和

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int n1 = a.size(), n2 = b.size();
        int c = 0;
        string ans;
        for(int i = 0; i < n1 || i < n2 || c != 0; i++)
        {
            int s = c;
            if(i < n1) s += a[i] - '0';
            if(i < n2) s += b[i] - '0';
            c = s / 2;
            s = s % 2;
            ans.push_back(s + '0');
        }
        while(ans.size() > 1 && ans.back() == '0')
            ans.pop_back();
        reverse(ans.begin(), ans.end());
        return ans;
    }
};